package com.hardy.job;

/**
 * @author fuxiaohui3@nuoyuan.com.cn
 * @date 2018/11/21 11:39
 * 实现一个函数，对一个正整数n，算得到1需要的最少操作次数。操作规则为：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。
 */
public class NumberCountOneNumbers {

    public int func1(int n) {
        int count = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                n >>= 1;
            } else if (n == 3) {
                n--;
            } else {
                if ((n & 2) == 0) {
                    n++;
                } else {
                    n--;
                }
            }
            count++;
        }
        return count;
    }

    public int func(int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return 1 + func(n / 2);
        }
        int x = func(n + 1);
        int y = func(n - 1);
        if (x > y) {
            return y + 1;
        } else {
            return x + 1;
        }
    }
}
